The present invention relates to computer systems, and more particularly to a method for representing distributed and parallel computing systems based on process algebra and reducing the process algebra to a useful programming language for use in real world applications.
Transaction processing systems have led the way for many ideas in distributed computing and fault-tolerant computing. For example, transaction processing systems have introduced distributed data for reliability, availability, and performance, and fault tolerant storage and processes, in addition to contributing to the client-server model and remote procedure call for distributed computation. Importantly, transaction processing introduced the concept of transaction ACID propertiesxe2x80x94atomicity, consistency, isolation and durability that has emerged as the unifying concept for distributed computations. Atomicity refers to a transaction""s change to the state of the overall system happening all at once or not at all. Consistency refers to a transaction being a correct transformation of the system state and essentially means that the transaction is a correct program. Although transactions execute concurrently, isolation ensures that transactions appear to execute before or after another transaction because intermediate states of transactions are not visible to other transactions (e.g., locked during execution). Durability refers to once a transaction completes successfully (commits) its activities or its changes to the state become permanent and survive failures.
Many applications for workflow tools are internal to a business or organization. With the advent of networked computers and modems, computer systems at remote locations can now easily communicate with one another. This allows computer system workflow applications to be used between remote facilities within a company. Workflow applications can also be of particular utility in processing business transactions between different companies. Automating such processes can result in significant efficiency improvements, not otherwise possible. However, this inter-company application of workflow technology requires co-operation of the companies and proper interfacing of the individual company""s existing computer systems.
Many attempts at description languages for business workflow process have been made. These languages target specifications of distributed and concurrent systems for the purpose of systems integration. The extensible markup language (XML) has been designed for system integration. XML is a meta-markup language that provides a format for describing structured data. An XML element can declare its associated data to be a retail price, a sales tax, a book title, or any desired data element. XML provides a structural representation of data that has proved broadly implementable and easy to deploy. A piece of information marked by the presence of tags is called an element. Elements can be further described by attaching name value pairs called attributes. Once the data is received by the client, the data can be manipulated edited and presented in multiple ways without being sent back to the server. The XML syntax uses matching start and end tags to mark up information. Presently, XML has been applied to the representations of applications data (e.g., business documents, EDI messages). Efforts have been made by the Workflow Management Consortium to describe business processes with XML. However, none of these descriptions have provided a compelling and theoretically sound framework for description of system behavior.
Accordingly, there is a strong need in the art for a method for providing a sound framework for business workflow process applications in addition to providing a sound framework in the broad domain of distributed and parallel computing.
The present invention relates to a methodology for encoding mobile process calculi into XML. Mobile process calculi (e.g., xcfx80-calculus, Join Calculus, Blue Calculus) are ideally suited for modeling a wide variety of processes, including business processes. The present invention provides for encoding the grammar of a mobile process algebra as an XML schema. The invention takes a representation of the grammar of a mobile process algebra, for example an EBNF specification, and reformulates the process algebra syntax to infix notation, and then transforming the prefix notation to a set of tags via structural induction. Annotating tags can then be provided around basic process algebra constructors. For example, tags introducing other semantic constraints, e.g. transaction boundaries or continuations may be introduced with minimal impact on the basic structure of the process algebra representation. As mentioned, the set of tags represent an XML schema. If the process algebra has an executable semantics, then the XML schema can then be provided as a textual and machine-readable format of a programming language. An example of reducing a specific algebra (combinatorsxe2x80x94a derivative of xcfx80-calculus) to an XML schema is provided below. The XML schema is reduced to a programming language ideal for business workflow processes. An example of a business process employing the programming language is also provided herein.
The present invention also includes a new process algebra that is tailored to support domains of processes, like business processes, that have requirements for concurrent join and transaction semantics. The new process algebra considered in the present invention is unique in that it not only provides expression for sequencing, branching and parallelism, but also distinguishes isolated parallelism and communicating parallelism, provides types of concurrency and provides a polymorphic specification as an effective procedure for testing message equality. Furthermore, the present invention affords the ability to separate dataflow from control flow, thus allowing encoding of the process algebra to focus on expression of control flow constraints.
In one aspect of the invention, a method of producing a schema for a domain of process algebra is provided. The method comprises the steps of transforming the process algebra from infix notation to prefix notation and transforming the prefix notation to a set of tags, wherein the set of tags represent a schema.
In another aspect of the invention a method is provided of producing an XML schema for a domain of process algebra. The method comprises the steps of transforming the process algebra from infix notation to prefix notation and transforming the prefix notation to a set of XML tags via structural induction, wherein the set of tags represent a schema.
In yet another aspect of the invention an XML schema is provided. The XML schema comprises a first element representing a construct for distinguishing between synchronization of autonomous concurrent operations from interdependent concurrent operations and a second element representing a construct for interdependent operations.
In another aspect of the invention, a software module is provided. The software module comprises a receiving component adapted to receive a specification of the grammar of a process algebra, for example a specification in EBNF, a construct component adapted to provide a construct for each operator in the process algebra and an output component adapted to output the constructs corresponding to the process algebra operators.
In an alternate aspect of the invention a system is provided for providing a schema from a process algebra. The system comprises means for inputting a process algebra, means for providing a plurality of constructs corresponding to operators in the process algebra and means for outputting the plurality of constructs.
In one aspect of the invention, a system for producing a schema for a domain of process algebra is provided. The system comprises a subsystem for transforming the process algebra from infix notation to prefix notation and a subsystem for transforming the prefix notation to a set of tags, wherein the set of tags represent a schema.
In another aspect of the invention, a system for producing a schema for a domain of process algebra is provided. The system comprises means for transforming the process algebra from infix notation to prefix notation and means for transforming the prefix notation to a set of tags, wherein the set of tags represent a schema.
To the accomplishment of the foregoing and related ends, the invention then, comprises the features hereinafter fully described and particularly pointed out in the claims. The following description and the annexed drawings set forth in detail certain illustrative embodiments of the invention. These embodiments are indicative, however, of but a few of the various ways in which the principles of the invention may be employed and the present invention is intended to include all such embodiments and their equivalents. Other objects, advantages and novel features of the invention will become apparent from the following detailed description of the invention when considered in conjunction with the drawings.